Search Results

Documents authored by Zaroliagis, Christos

Found 2 Possible Name Variants:

Zaroliagis, Christos

Document
DOI: 10.4230/OASIcs.ATMOS.2022.12
REX: A Realistic Time-Dependent Model for Multimodal Public Transport

Authors: Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.
Cite as

Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis. REX: A Realistic Time-Dependent Model for Multimodal Public Transport. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2022.12,
  author =	{Kontogiannis, Spyros and Machaira, Paraskevi-Maria-Malevi and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{REX: A Realistic Time-Dependent Model for Multimodal Public Transport}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{12:1--12:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.12},
  URN =		{urn:nbn:de:0030-drops-171164},
  doi =		{10.4230/OASIcs.ATMOS.2022.12},
  annote =	{Keywords: multimodal journey planning, REX model, TRIPLA query algorithm, schedule-based timetables}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.9
Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations

Authors: Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We aim at exploiting parallelism in shared-memory multiprocessing systems, in order to speed up the execution time with as small redundancy in work as possible, for an elementary task that comes up frequently as a subroutine in the daily maintenance of large-scale time-dependent graphs representing real-world relationships or technological networks: the many-to-all time-dependent shortest paths (MATDSP) problem. MATDSP requires the computation of one time-dependent shortest-path tree (TDSPT) per origin-vertex and departure-time, from an arbitrary collection of pairs of origins and departure-times, towards all reachable destinations in the graph. Our goal is to explore the potential and highlight the limitations of amorphous data parallelism, when dealing with MATDSP in multicore computing environments with a given amount of processing elements and a shared memory to exploit. Apart from speeding-up execution time, consumption of resources (and energy) is also critical. Therefore, we aim at limiting the work overhead for solving a MATDSP instance, as measured by the overall number of arc relaxations in shortest-path computations, while trying to minimize the overall execution time. Towards this direction, we provide several algorithmic engineering interventions for solving MATDSP concerning: (i) the compact representation of the instance; (ii) the choice and the improvement of the time-dependent single-source shortest path algorithm that is used as a subroutine; (iii) the way according to which the overall work is allocated to the processing elements; (iv) the adoption of the amorphous data parallelism rationale, in order to avoid costly synchronization among the processing elements while doing their own part of the work. Our experimental evaluations, both on real-world and on synthetic benchmark instances of time-dependent road networks, provide insight how one should organize heavy MATDSP computations, depending on the application scenario. This insight is in some cases rather unexpected. For instance, it is not always the case that pure data parallelism (among otherwise totally independent processors) is the best choice for minimizing execution times. In certain cases it may be worthwhile to limit the level of data parallelism in favor of algorithmic parallelism, in order to achieve more efficient MATDSP computations.
Cite as

Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis. Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2019.9,
  author =	{Kontogiannis, Spyros and Papadopoulos, Anastasios and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{9:1--9:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.9},
  URN =		{urn:nbn:de:0030-drops-114210},
  doi =		{10.4230/OASIcs.ATMOS.2019.9},
  annote =	{Keywords: amorphous data parallelism, delta-stepping algorithm, travel-time oracle, many-to-all shortest paths, time-dependent road networks}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.4
Improved Oracles for Time-Dependent Road Networks

Authors: Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
Cite as

Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2017.4,
  author =	{Kontogiannis, Spyros and Papastavrou, Georgia and Paraskevopoulos, Andreas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Improved Oracles for Time-Dependent Road Networks}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.4},
  URN =		{urn:nbn:de:0030-drops-78954},
  doi =		{10.4230/OASIcs.ATMOS.2017.4},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.47
Hierarchical Time-Dependent Oracles

Authors: Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study networks obeying time-dependent min-cost path metrics, and present novel oracles for them which provably achieve two unique features: (i) subquadratic preprocessing time and space, independent of the metric’s amount of disconcavity; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand.
Cite as

Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis. Hierarchical Time-Dependent Oracles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:LIPIcs.ISAAC.2016.47,
  author =	{Kontogiannis, Spyros and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Hierarchical Time-Dependent Oracles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.47},
  URN =		{urn:nbn:de:0030-drops-68170},
  doi =		{10.4230/LIPIcs.ISAAC.2016.47},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ESA.2016
LIPIcs, Volume 57, ESA'16, Complete Volume

Authors: Piotr Sankowski and Christos Zaroliagis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
LIPIcs, Volume 57, ESA'16, Complete Volume
Cite as

24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{sankowski_et_al:LIPIcs.ESA.2016,
  title =	{{LIPIcs, Volume 57, ESA'16, Complete Volume}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016},
  URN =		{urn:nbn:de:0030-drops-65854},
  doi =		{10.4230/LIPIcs.ESA.2016},
  annote =	{Keywords: Data Structures, Nonnumerical Algorithms and Problems, Optimization, Discrete Mathematics, Mathematical Software, Algorithms, Problem Solving, Control Methods and Search, Computational Geometry and Object Modeling}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ESA.2016.0
Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers

Authors: Piotr Sankowski and Christos Zaroliagis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers
Cite as

24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 0:i-0:xxiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sankowski_et_al:LIPIcs.ESA.2016.0,
  author =	{Sankowski, Piotr and Zaroliagis, Christos},
  title =	{{Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{0:i--0:xxiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.0},
  URN =		{urn:nbn:de:0030-drops-63429},
  doi =		{10.4230/LIPIcs.ESA.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.46
Engineering Graph-Based Models for Dynamic Timetable Information Systems

Authors: Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to be used in combination with speed-up techniques developed for road networks. In this paper, we focus on the dynamic behavior of graph-based models considering the case where transportation systems are subject to delays with respect to the given timetable. We make three contributions: (i) we give a simplified and optimized update routine for the well-known time-expanded model along with an engineered query algorithm; (ii) we propose a new graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of the proposed models and algorithms by an experimental study, which shows that both models require negligible update time and a query time which is comparable to that required by some array-based models.
Cite as

Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Engineering Graph-Based Models for Dynamic Timetable Information Systems. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 46-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cionini_et_al:OASIcs.ATMOS.2014.46,
  author =	{Cionini, Alessio and D'Angelo, Gianlorenzo and D'Emidio, Mattia and Frigioni, Daniele and Giannakopoulou, Kalliopi and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Engineering Graph-Based Models for Dynamic Timetable Information Systems}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{46--61},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.46},
  URN =		{urn:nbn:de:0030-drops-47522},
  doi =		{10.4230/OASIcs.ATMOS.2014.46},
  annote =	{Keywords: Timetabling, dynamic updates, queries, shortest paths}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.108
Improved Alternative Route Planning

Authors: Andreas Paraskevopoulos and Christos Zaroliagis

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
We present improved methods for computing a set of alternative source-to-destination routes in road networks in the form of an alternative graph. The resulting alternative graphs are characterized by minimum path overlap, small stretch factor, as well as low size and complexity. Our approach improves upon a previous one by introducing a new pruning stage preceding any other heuristic method and by introducing a new filtering and fine-tuning of two existing methods. Our accompanying experimental study shows that the entire alternative graph can be computed pretty fast even in continental size networks.
Cite as

Andreas Paraskevopoulos and Christos Zaroliagis. Improved Alternative Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 108-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{paraskevopoulos_et_al:OASIcs.ATMOS.2013.108,
  author =	{Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Improved Alternative Route Planning}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{108--122},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.108},
  URN =		{urn:nbn:de:0030-drops-42485},
  doi =		{10.4230/OASIcs.ATMOS.2013.108},
  annote =	{Keywords: Alternative route, stretch factor, shortest path, non-overlapping path, penalty, plateau}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2145
Efficient Route Planning in Flight Networks

Authors: Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
We present a set of three new time-dependent models with increasing flexibility for realistic route planning in flight networks. By these means, we obtain small graph sizes while modeling airport procedures in a realistic way. With these graphs, we are able to efficiently compute a set of best connections with multiple criteria over a full day. It even turns out that due to the very limited graph sizes it is feasible to precompute full distance tables between all airports. As a result, best connections can be retrieved in a few microseconds on real world data.
Cite as

Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis. Efficient Route Planning in Flight Networks. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2009.2145,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Efficient Route Planning in Flight Networks}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2145},
  URN =		{urn:nbn:de:0030-drops-21450},
  doi =		{10.4230/OASIcs.ATMOS.2009.2145},
  annote =	{Keywords: Timetable information, flight modeling, shortest paths, multi criteria, table lookups Timetable information, flight modeling, shortest paths, multi criteria, table lookups}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2146
On Assessing Robustness in Transportation Planning

Authors: Apostolos Bessas and Christos Zaroliagis

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
We consider a fundamental problem, called \emph{QoS-aware Multicommodity Flow}, for assessing robustness in transportation planning. It constitutes a natural generalization of the weighted multicommodity flow problem, where the demands and commodity values are elastic to the Quality-of-Service (QoS) characteristics of the underlying network. The problem is also fundamental in other domains beyond transportation planning. In this work, we provide an extensive experimental study of two FPTAS for the QoS-aware Multicommodity Flow Problem enhanced with several heuristics, and show the superiority of a new heuristic we introduce here.
Cite as

Apostolos Bessas and Christos Zaroliagis. On Assessing Robustness in Transportation Planning. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bessas_et_al:OASIcs.ATMOS.2009.2146,
  author =	{Bessas, Apostolos and Zaroliagis, Christos},
  title =	{{On Assessing Robustness in Transportation Planning}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2146},
  URN =		{urn:nbn:de:0030-drops-21469},
  doi =		{10.4230/OASIcs.ATMOS.2009.2146},
  annote =	{Keywords: QoS-ware Multicommodity Flow, Robust Planning, Demand Elasticity, Packing LP QoS-ware Multicommodity Flow, Robust Planning, Demand Elasticity, Packing LP}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1581
Robust Line Planning under Unknown Incentives and Elasticity of Frequencies

Authors: Spyros Kontogiannis and Christos Zaroliagis

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
The problem of robust line planning requests for a set of origin-destination paths (lines) along with their traffic rates (frequencies) in an underlying railway network infrastructure, which are robust to fluctuations of real-time parameters of the solution. In this work, we investigate a variant of robust line planning stemming from recent regulations in the railway sector that introduce competition and free railway markets, and set up a new application scenario: there is a (potentially large) number of line operators that have their lines fixed and operate as competing entities struggling to exploit the underlying network infrastructure via frequency requests, while the management of the infrastructure itself remains the responsibility of a single (typically governmental) entity, the network operator. The line operators are typically unwilling to reveal their true incentives. Nevertheless, the network operator would like to ensure a fair (or, socially optimal) usage of the infrastructure, e.g., by maximizing the (unknown to him) aggregate incentives of the line operators. We show that this can be accomplished in certain situations via a (possibly anonymous) incentive- compatible pricing scheme for the usage of the shared resources, that is robust against the unknown incentives and the changes in the demands of the entities. This brings up a new notion of robustness, which we call incentive-compatible robustness, that considers as robustness of the system its tolerance to the entities' unknown incentives and elasticity of demands, aiming at an eventual stabilization to an equilibrium point that is as close as possible to the social optimum.
Cite as

Spyros Kontogiannis and Christos Zaroliagis. Robust Line Planning under Unknown Incentives and Elasticity of Frequencies. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2008.1581,
  author =	{Kontogiannis, Spyros and Zaroliagis, Christos},
  title =	{{Robust Line Planning under Unknown Incentives and Elasticity of Frequencies}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1581},
  URN =		{urn:nbn:de:0030-drops-15813},
  doi =		{10.4230/OASIcs.ATMOS.2008.1581},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/OASIcs.ATMOS.2006.682
QoS-aware Multicommodity Flows and Transportation Planning

Authors: George Tsaggouris and Christos Zaroliagis

Published in: OASIcs, Volume 5, 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (2006)

Abstract
We consider the emph{QoS-aware Multicommodity Flow} problem, a natural generalization of the weighted multicommodity flow problem where the demands and commodity values are elastic to the Quality-of-Service characteristics of the underlying network. The problem is fundamental in transportation planning and also has important applications beyond the transportation domain. We provide a FPTAS for the QoS-aware Multicommodity Flow problem by building upon a Lagrangian relaxation method and a recent FPTAS for the non-additive shortest path problem.
Cite as

George Tsaggouris and Christos Zaroliagis. QoS-aware Multicommodity Flows and Transportation Planning. In 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06). Open Access Series in Informatics (OASIcs), Volume 5, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{tsaggouris_et_al:OASIcs.ATMOS.2006.682,
  author =	{Tsaggouris, George and Zaroliagis, Christos},
  title =	{{QoS-aware Multicommodity Flows and Transportation Planning}},
  booktitle =	{6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-01-9},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{5},
  editor =	{Jacob, Riko and M\"{u}ller-Hannemann, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2006.682},
  URN =		{urn:nbn:de:0030-drops-6827},
  doi =		{10.4230/OASIcs.ATMOS.2006.682},
  annote =	{Keywords: Quality of service, multicommodity flows, fully polynomial approximation scheme, transportation planning}
}
Document
DOI: 10.4230/DagSemProc.04261.1
04261 Abstracts Collection – Algorithmic Methods for Railway Optimization

Authors: Leo G. Kroon, Dorothea Wagner, Frank Geraets, and Christos Zaroliagis

Published in: Dagstuhl Seminar Proceedings, Volume 4261, Algorithmic Methods for Railway Optimization (2006)

Abstract
From 20.06.04 to 25.06.04, the Dagstuhl Seminar 04261 ``Algorithmic Methods for Railway Optimization'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Leo G. Kroon, Dorothea Wagner, Frank Geraets, and Christos Zaroliagis. 04261 Abstracts Collection – Algorithmic Methods for Railway Optimization. In Algorithmic Methods for Railway Optimization. Dagstuhl Seminar Proceedings, Volume 4261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kroon_et_al:DagSemProc.04261.1,
  author =	{Kroon, Leo G. and Wagner, Dorothea and Geraets, Frank and Zaroliagis, Christos},
  title =	{{04261 Abstracts Collection – Algorithmic Methods for Railway Optimization}},
  booktitle =	{Algorithmic Methods for Railway Optimization},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4261},
  editor =	{Leo G. Kroon and Frank Geraets and Dorothea Wagner and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04261.1},
  URN =		{urn:nbn:de:0030-drops-4712},
  doi =		{10.4230/DagSemProc.04261.1},
  annote =	{Keywords: }
}

Zaroliagis, Christos D.

Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2020
OASIcs, Volume 85, ATMOS 2020, Complete Volume

Authors: Dennis Huisman and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
OASIcs, Volume 85, ATMOS 2020, Complete Volume
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1-272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{huisman_et_al:OASIcs.ATMOS.2020,
  title =	{{OASIcs, Volume 85, ATMOS 2020, Complete Volume}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{1--272},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020},
  URN =		{urn:nbn:de:0030-drops-131356},
  doi =		{10.4230/OASIcs.ATMOS.2020},
  annote =	{Keywords: OASIcs, Volume 85, ATMOS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dennis Huisman and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huisman_et_al:OASIcs.ATMOS.2020.0,
  author =	{Huisman, Dennis and Zaroliagis, Christos D.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.0},
  URN =		{urn:nbn:de:0030-drops-131363},
  doi =		{10.4230/OASIcs.ATMOS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.8
Time-Dependent Alternative Route Planning

Authors: Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.
Cite as

Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis. Time-Dependent Alternative Route Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2020.8,
  author =	{Kontogiannis, Spyros and Paraskevopoulos, Andreas and Zaroliagis, Christos D.},
  title =	{{Time-Dependent Alternative Route Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.8},
  URN =		{urn:nbn:de:0030-drops-131441},
  doi =		{10.4230/OASIcs.ATMOS.2020.8},
  annote =	{Keywords: time-dependent shortest path, alternative routes, travel-time oracle, plateau and penalty methods}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact